/*
 * @lc app=leetcode.cn id=365 lang=typescript
 *
 * [365] 水壶问题
 */

// @lc code=start

class Data {
  constructor(public x: number, public y: number) {
    this.x = x;
    this.y = y;
  }

  next(type: number, x: number, xmax: number, y: number, ymax: number) {
    switch (type) {
      case 0:
        // 第一个壶灌满
        return new Data(xmax, y);
      case 1:
        // 第二个壶灌满
        return new Data(x, ymax);
      case 2:
        // 第一个壶里的水清空
        return new Data(0, y);
      case 3: {
        // 第一个壶往第二个壶倒入一部分水
        let diff = Math.min(x, ymax - y);
        return new Data(x - diff, y + diff);
      }
      case 4:
        // 第二个壶里的水清空
        return new Data(x, 0);
      case 5: {
        // 第二个壶往第一个壶倒入一部分水
        let diff = Math.min(xmax - x, y);
        return new Data(x + diff, y - diff);
      }
    }
  }
}

function canMeasureWater(
  jug1Capacity: number,
  jug2Capacity: number,
  targetCapacity: number
): boolean {
  const deque = [];
  const visited = new Set();
  deque.push(new Data(0, 0));
  visited.add(`0#0`);
  while (deque.length) {
    const data: Data = deque.shift();
    // 满足目标值
    if (data.x + data.y === targetCapacity) return true;
    // 扩展状态，注意需要将访问过的状态过滤掉
    for (let i = 0; i < 6; i++) {
      const next: Data = data.next(i, data.x, jug1Capacity, data.y, jug2Capacity);
      const key = `${next.x}#${next.y}`;
      if (visited.has(key)) continue;
      visited.add(key);
      deque.push(next);
    }
  }

  return false;
}
// @lc code=end
